/*
 * @lc app=leetcode.cn id=74 lang=java
 *
 * [74] 搜索二维矩阵
 */

// @lc code=start
class Solution {
    //二分查找矩阵版？
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length , n = matrix[0].length;
        if(matrix[0][0]>target || matrix[m-1][n-1]<target) return false;
        int left = 0 ,right = m*n-1;
        while(left<right){
            int mid = (right+left)/2;
            int temp = matrix[mid/n][mid%n];//将mid映射到矩阵的位置
            if(temp==target) return true;
            else if(temp<target) left = mid+1;
            else right = mid-1;

        }
        if(matrix[right/n][right%n] == target || matrix[left/n][left%n]==target) return true;
        return false;
    }
}
// @lc code=end

